package lc20240605;


import java.util.*;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 课程表1
 * @date 2024/6/5 22:09
 */
public class Score {
    public static void main(String[] args) {
        int num = 3;
        int[][] pre = {
                {0, 1},
                {2, 0},
                {2, 1}
        };
        System.out.println(canFinish(num, pre));
    }

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        //初始化入度表
        int[] inDegree = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        //建立图和入度表
        for (int[] pair : prerequisites) {
            //后修课程
            int dest = pair[0];
            //先修课程
            int src = pair[1];
            graph.get(src).add(dest);
            //更新入度表
            inDegree[dest] += 1;
        }

        //3.用所有入度为0的点初始化队列。
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        //4.用拓扑排序处理节点
        int visited = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            visited += 1;
            for (Integer neigh : graph.get(node)) {
                inDegree[neigh] -= 1;
                if (inDegree[neigh] == 0) {
                    queue.offer(neigh);
                }
            }
        }
        return visited == numCourses;
    }
}
